//给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。 
//
// 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。 
//
// 返回一个表示每个字符串片段的长度的列表。 
//
// 
//示例 1：
//
// 
//输入：s = "ababcbacadefegdehijhklij"
//输出：[9,7,8]
//解释：
//划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
//每个字母最多出现在一个片段中。
//像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 
//
// 示例 2： 
//
// 
//输入：s = "eccbbbbdec"
//输出：[10]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 500 
// s 仅由小写英文字母组成 
// 
//
// Related Topics 贪心 哈希表 双指针 字符串 👍 1014 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2023-09-14 11:21:09
 * @description 763.划分字母区间
 */
public class PartitionLabels{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new PartitionLabels().new Solution();
		solution.partitionLabels("ababcbacadefegdehijhklij");
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*用hashmap计数，然后依次遍历，当前用到的放到set中
		 * 如果计数为空，就从set中去除，如果set为空，就把当前序列加入答案*/
    public List<Integer> partitionLabels(String s) {
		List<Integer> res=new ArrayList<>();
		Map<Character,Integer> map=new HashMap<>();
		int l=0;
		for (Character c : s.toCharArray()) {
			map.put(c,map.getOrDefault(c,0)+1);
		}
		Set<Character> set=new HashSet<>();
		set.add(s.charAt(0));
		for (int i=0;i<s.length();i++) {
			set.add(s.charAt(i));
			int count = map.get(s.charAt(i));
			if(--count==0){
				set.remove(s.charAt(i));
			}
			if(set.isEmpty()){
				res.add(i-l+1);
				l=i+1;
			}
			map.put(s.charAt(i),count);
		}
		return res;
    }

	/*不需要计数，只需要考虑最后一次出现的位置*/
	public List<Integer> partitionLabels1(String s) {
		List<Integer> res=new ArrayList<>();
		Map<Character,Integer> map=new HashMap<>();
		int l=0,r=0;
		for (int i = 0; i < s.length(); i++) {
			map.put(s.charAt(i),i);
		}
		for (int i = 0; i < s.length(); i++) {
			//到达了所有一系列字母里最远的位置时这个序列分割
			r= Math.max(r,map.get(s.charAt(i)));
			if(i==r){
				res.add(r-l+1);
				l=i+1;
			}
		}
		return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
